package com.lw.leetcode.stack.b;

import java.util.Stack;

/**
 * 331. 验证二叉树的前序序列化
 *
 * @Author liw
 * @Date 2021/5/17 17:24
 * @Version 1.0
 */
public class IsValidSerialization {

    public static void main(String[] args) {
        IsValidSerialization test = new IsValidSerialization();
        boolean validSerialization = test.isValidSerialization("#");
//        boolean validSerialization = test.isValidSerialization("1,#");
        System.out.println(validSerialization);
    }

    public boolean isValidSerialization(String preorder) {
        if (preorder == null) {
            return false;
        }
        String[] arr = preorder.split(",");
        int length = arr.length;
        String value = arr[0];
        if ("#".equals(value)) {
            return length == 1;
        }
        Stack<String> stack = new Stack<>();
        stack.add(value);

        for (int i = 1; i < length; i++) {
            value = arr[i];
            while (!stack.isEmpty() && "#".equals(value) && "#".equals(stack.peek())) {
                stack.pop();
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
                value = "#";
            }
            if (stack.isEmpty() && i == length - 1) {
                return true;
            }
            stack.add(arr[i]);

        }
        return stack.isEmpty();
    }
}
